1. Field of the Invention
This invention relates to the fields of generic programming and parallel programming, and more particularly to a generic adaptor for converting from a sequential iterator to a parallel iterator.
2. Description of the Related Art
Parallel programming or parallel processing is a method of processing that executes on a computer containing two or more processors running simultaneously. A primary objective of parallel processing is dividing a task so that it may be distributed among the available processors.
Object oriented programming languages such as C and C++ support arrays which are contiguous address spaces, and pointers that may be used to traverse these arrays. An iterator is a generalization of a pointer that allows a programmer to work with different data structures or containers in a uniform manner. Generic programming, such as the Standard Template Library or STIL, may provide iterators that are objects with operators that allow traversal of the data structures they point to and also operators that allow accessing the content at the current position pointed to by the iterator. STL defines different iterator categories such as input, output, forward, backward, and random access. This categorization is based on iterator properties such as direction of traversal, quantum of traversal, readability, or writability into the data structures to which an iterator points. An STL iterator is inherently sequential in nature because each iterator defines a single cursor of traversal and update. This sequential single cursor iterator is inadequate for the non-sequential multi-task needs of parallel programming.
HPC++ is a C++ library and language extension framework for parallel programming. HPC++ extends iterators for use in parallel programming in distributed address spaces. HPC++ provides distributed containers which are template data structures distributed over multiple computer address spaces. These distributed containers provide iterators that allow the traversal of the entire range of a distributed container across different address spaces. For each address space, HPC++ adaptor functions may return local iterators which mark the range of a portion of the distributed container within the local address space. Thus HPC++ parallel iterators are based on distributed address spaces for different data distributions of distributed containers. However, HPC++ parallel iterators fail to provide support based on task distribution. HPC++parallel iterators also fail to provide different parallel algorithm implementations for different task or data distributions for supporting needs of correctness or efficiency.
Although HPC++ fails to provide task distribution strategies, there are other parallel programming libraries which provide task distribution strategies. However, these parallel programming libraries fail to provide generic parallel task distribution strategies.
In providing parallel implementations of algorithms, conventional systems have failed to recognize the benefits of designing an implementations in such a way that different strategies of work distribution may be made a part of the algorithm implementation. In sequential programming, the conventional STL system reduces N*M*K possible implementations for N data types, M containers, and K algorithms to possibly N+M+K implementations. However, conventional parallel programming has failed to recognize that if there are P strategies of work distribution for N data types, M containers, and K algorithms, that the N*M*K*P possible parallel implementations may be reduced to N+M+K+P implementations.
Despite the above developments and benefits of both parallel programming and generic programming, both have failed to recognize the need for or provide a solution of a generic abstraction which may convert a sequential iterator to a parallel iterator with a parallel work distribution strategy to further the reuse of sequential algorithms in corresponding parallel implementations. As such, there is a need for a method of, apparatus for, and article of manufacture for providing a generic adaptor for converting from a sequential iterator to a parallel iterator with a parallel work distribution strategy.